package com.fantaike.algorithm.sort;

/**
 * 插入排序：
 * 1. 插入排序将数组拆分成两部分一部分是以排序，另一部分是未排序
 * 2. 第一次默认将数组索引0处的是当作以排序，而索引1及以后部分当作未排序
 * 3. 拿出未排序的要和以排序后的倒叙进行比较，未排序的大就不需要交换，若是已排序的大那么就要进行交换
 * 交换后，接着和已排序的前一个比较直到找到位置及可
 * @author jishushen
 * @create 2021-07-31 15:55
 */
public class Insertion {

    /**
     * @Description: 插入排序
     * @param array
     * @Date: 2021/7/31 20:53
     * @Author: xuepeng
     * @Return
     * @Throws
     */
    public static void sort(Comparable[] array){
        for (int i = 1; i < array.length; i++) {
            for (int j = i; j > 0 ; j--) {
                //比较索引j处的值和j-1处的值，如果j-1处的值比索引j处的值大，则交换数据，如果不大那么就找到对应的位置了，退出循环即可
                if (greater(array[j-1],array[j])){
                    exch(array,j-1,j);
                }else {
                    break;
                }
            }
        }
    }


    /**
     * @Description: v和w进行比较，如果v比w大就返回true
     * @param v
     * @param w
     * @Date: 2021/7/31 13:46
     * @Author: xuepeng
     * @Return
     * @Throws
     */
    public static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w) > 0;
    }

    /**
     * @Description: 索引i处的值和索引j处的值进行交换
     * @param array
     * @param i
     * @param j
     * @Date: 2021/7/31 13:48
     * @Author: xuepeng
     * @Return
     * @Throws
     */
    public static void exch(Comparable[] array,int i,int j){
        Comparable temp;
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }


}
